package sorting;

import util.Tracer;


public class VariableLengthRadixSort {
	public static int[] sort(int[] numbers)
	{
		int[] sorted = new int[numbers.length];
		int[] countAux = new int[10];
		sort(numbers, sorted, countAux, 0, numbers.length - 1, 0);
		return sorted;
	}
	
	private static void sort(int[] numbers, int[] sorted, int[] countAux, int from, int to, int digit)
	{
		for(int i = 0; i < 10; i ++)
		{
			countAux[i] = 0;
		}

		int newFrom = from;
		for(int i = from; i <= to; i ++)
		{
			int number = numbers[i];
			if(getDigits(number) > digit)
			{
				countAux[getDigit(numbers[i], digit)] ++;
			}
			else
			{
				sorted[newFrom] = number;
				newFrom ++;
			}
		}
		
		if(newFrom > to)
			return;
		
		countAux[0] = newFrom + countAux[0];
		for(int i = 1; i < 10; i ++)
		{
			countAux[i] += countAux[i - 1];
		}
		
		for(int i = to; i >= from; i --)
		{
			int number = numbers[i];
			if(getDigits(number) > digit)
			{
				sorted[-- countAux[getDigit(number, digit)]] = number;
			}
		}
		
		for(int i = newFrom; i <= to; i ++)
		{
			numbers[i] = sorted[i];
		}
		
		sort(numbers, sorted, countAux, newFrom, to, digit + 1);
	}
	
	private static int getDigits(int number)
	{
		return (int)Math.log10(number) + 1;
	}

	private static int getDigit(int number, int digit)
	{
		return (number / (int)Math.pow(10, digit)) % 10;
	}
	
	public static void main(String[] args) {
		int[] sorted = sort(new int[]{115, 112, 113, 1145, 1, 4, 8,1222, 1888, 111, 10000, 10});
		Tracer.trace(sorted);
	}
}